'lintcode 丢鸡蛋2'

Posted on | In

lintcode 丢鸡蛋2

描述

有一个n层的建筑。如果一个鸡蛋从第k层及以上落下，它会碎掉。如果从低于这一层的任意层落下，都不会碎。
有m个鸡蛋，用最坏的情况下实验次数最少的方法去找到k, 返回最坏情况下所需的实验次数。

样例

Example 1:

Input: m = 2, n = 100
Output: 14
Example 2:

Input: m = 2, n = 36
Output: 8

思路

利用动态规划，dp[i][j]表示i个鸡蛋试验j层楼。
对于任意一次dp[i][j]，第一次尝试在k层，那么dp[i][j] = 1+max(dp[ i ][ j - k ], dp[ i - 1 ][ k - 1]).
找最大值是考虑到最坏情况，要找的k是最优k，即要让dp[i][j]最小。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    /**
     * @param m: the number of eggs
     * @param n: the number of floors
     * @return: the number of drops in the worst case
     */
    int dropEggs2(int m, int n) {
        // write your code here
        int dp[m+1][n+1];
        for (int i = 0; i < m+1; i++) {
            for (int j = 0; j < n+1; j++)
                dp[i][j] = INT_MAX;
        }
        for (int i = 0; i < n+1; i++) {
            dp[1][i] = i;
            dp[0][i] = 0;
        }
        for (int i = 0; i < m+1; i++) {
            dp[i][0] = 0;
            dp[i][1] = 1;
            dp[i][2] = 2;
        }
        for (int i = 2; i < m+1; i++) {
            for (int j = 2; j < n+1; j++) {
                for (int k = 2; k < n; k++) {
                    dp[i][j] = min(dp[i][j], 1+max(dp[i][j-k], dp[i-1][k-1]));
                }
            }
        }
        return dp[m][n];
    }
};
-------------end of filethanks for reading-------------